Approximate message passing algorithms proved to be extremely effective inreconstructing sparse signals from a small number of incoherent linearmeasurements. Extensive numerical experiments further showed that theirdynamics is accurately tracked by a simple one-dimensional iteration termedstate evolution. In this paper we provide the first rigorous foundation tostate evolution. We prove that indeed it holds asymptotically in the largesystem limit for sensing matrices with independent and identically distributedgaussian entries. While our focus is on message passing algorithms for compressed sensing, theanalysis extends beyond this setting, to a general class of algorithms on densegraphs. In this context, state evolution plays the role that density evolutionhas for sparse graphs. The proof technique is fundamentally different from the standard approach todensity evolution, in that it copes with large number of short loops in theunderlying factor graph. It relies instead on a conditioning technique recentlydeveloped by Erwin Bolthausen in the context of spin glass theory.
展开▼
